import java.security.KeyPair;
import java.util.ArrayList;
import java.util.List;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}
public class LeetCode {
    public int widthOfBinaryTree1(TreeNode root) {
        int res = 1;
        List<Pair<TreeNode, Integer>> arr = new ArrayList<Pair<TreeNode, Integer>>();
        arr.add(new Pair<TreeNode, Integer>(root, 1));
        while (!arr.isEmpty()) {
            List<Pair<TreeNode, Integer>> tmp = new ArrayList<Pair<TreeNode, Integer>>();
            for (Pair<TreeNode, Integer> pair : arr) {
                TreeNode node = pair.getKey();
                int index = pair.getValue();
                if (node.left != null) {
                    tmp.add(new Pair<TreeNode, Integer>(node.left, index * 2));
                }
                if (node.right != null) {
                    tmp.add(new Pair<TreeNode, Integer>(node.right, index * 2 + 1));
                }
            }
            res = Math.max(res, arr.get(arr.size() - 1).getValue() - arr.get(0).getValue() + 1);
            arr = tmp;
        }
        return res;


    }
    public int widthOfBinaryTree(TreeNode root) {
        List<Pair<TreeNode,Integer>> q = new ArrayList<>();
        q.add(new Pair<>(root,1));
        int ret = 0;
        while(!q.isEmpty()){
            Pair<TreeNode,Integer> q1 = q.get(0);
            Pair<TreeNode,Integer> qn = q.get(q.size()-1);
            ret = Math.max(ret,qn.getValue()-q1.getValue()+1);
            List<Pair<TreeNode,Integer>> tmp = new ArrayList<>();
            for(Pair<TreeNode,Integer> a:q){
                TreeNode node = a.getKey();
                int val = a.getValue();
                if(node.left!=null){
                    tmp.add(new Pair<>(node.left,2*val));
                }
                if(node.right!=null){
                    tmp.add(new Pair<>(node.right,2*val+1));
                }
            }
            q = tmp;
        }
        return ret;

    }
}
